#include <iostream>
#include <stdio.h>
#include <malloc.h>
#define TRUE 1
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
using namespace std;

typedef int Status;
typedef int ElemType;

typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

typedef struct stack
{
    BiTree *base;
    BiTree *top;
    int stacksize;
}SqStack;

typedef struct queuenode
{
    BiTree ch;
    struct queuenode *next;
}queuenode,*queueptr;

typedef struct
{
    queueptr front;
    queueptr rear;
}linkqueue;

Status InsertBiT(BiTree *T,int k)
{
    BiTNode *q,*p=*T;
    while(p)
    {
        if(p->data==k)
            return ERROR;
        q=p;
        p=(k<p->data)?p->lchild:p->rchild;
    }
    p=(BiTNode*)malloc(sizeof(BiTNode));
    p->data=k;
    p->lchild=p->rchild=NULL;
    if(*T==NULL)
        *T=p;
    else
        if(k<q->data)
            q->lchild=p;
        else
            q->rchild=p;
    return OK;
}

BiTree CreateBiT(int n)
{
    BiTree T=NULL;
    int k,i;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&k);
        InsertBiT(&T,k);
    }
    return T;
}

Status Visit(ElemType e)
{
    printf("%d ",e);
    return OK;
}

Status PreOrderTraverse(BiTree T)
{
    if(T)
    {
        if(Visit(T->data))
            if(PreOrderTraverse(T->lchild))
                if(PreOrderTraverse(T->rchild))
                    return OK;
        return ERROR;
    }
    else
        return OK;
}

Status InOrderTraverse(BiTree T)
{
    if(T)
    {
        if(InOrderTraverse(T->lchild))
            if(Visit(T->data))
                if(InOrderTraverse(T->rchild))
                    return OK;
        return ERROR;
    }
    else
        return OK;
}

Status PostOrderTraverse(BiTree T)
{
    if(T)
    {
        if(PostOrderTraverse(T->lchild));
            if(PostOrderTraverse(T->rchild));
                if(Visit(T->data))
                    return OK;
        return ERROR;
    }
    else
        return OK;
}

Status Visits(ElemType e,int m,int &t)
{
    if(e==m)
        t=1;
    return OK;
}

Status PostSearch(BiTree T,int m,int &t)
{
    if(T)
    {
        if(PostSearch(T->lchild,m,t))
            if(PostSearch(T->rchild,m,t))
                if(Visits(T->data,m,t))
                    return OK;
        return ERROR;
    }
    else
        return OK;
}



void initqueue(linkqueue &q)
{
    q.front=q.rear=(queueptr)malloc(sizeof(queuenode));
    q.front->next=NULL;
}

void enqueue(linkqueue &q,BiTree p)
{
    queueptr s;
    s=(queueptr)malloc(sizeof(queuenode));
    s->ch=p;
    s->next=NULL;
    q.rear->next=s;
    q.rear=s;
}

void dequeue(linkqueue &q,BiTree &p)
{
    int data;
    queueptr s;
    s=q.front->next;
    p=s->ch;
    data=p->data;
    q.front->next=s->next;
    if(q.rear==s)
        q.rear=q.front;
    free(s);
    printf("%d ",data);
}

int queueempty(linkqueue q)
{
    if(q.front->next==NULL)
        return 1;
    else
        return 0;
}

void traverse(BiTree bt)
{
    linkqueue q;
    BiTree p;
    initqueue(q);
    p=bt;
    enqueue(q,p);
    while(queueempty(q)!=1)
    {
        dequeue(q,p);
        if(p->lchild!=NULL)
            enqueue(q,p->lchild);
        if(p->rchild!=NULL)
            enqueue(q,p->rchild);
    }
    printf("\n");
}

Status Exchange(BiTree &T)
{
    BiTree p;
    if(T)
    {
        p=T->lchild;
        T->lchild=T->rchild;
        T->rchild=p;
        Exchange(T->lchild);
        Exchange(T->rchild);
    }
    return OK;
}

Status Depth(BiTree T)
{
    int depthval,depthLeft,depthRight;
    if(!T)
        depthval=0;
    else
    {
        depthLeft=Depth(T->lchild);
        depthRight=Depth(T->rchild);
        depthval=1+(depthLeft>depthRight?depthLeft:depthRight);
    }
    return depthval;
}

Status countieaf(BiTree T,int &n)
{
    if(T)
    {
        if(T->lchild==NULL&&T->rchild==NULL)
            n++;
        countieaf(T->lchild,n);
        countieaf(T->rchild,n);
    }
    return OK;
}


int main()
{
    int m1,m2,n,i,t=0,k=0;
    BiTree T;
    scanf("%d",&n);
    T=CreateBiT(n);
    scanf("%d%d%d",&m1,&m2,&i);
    PreOrderTraverse(T);
    printf("\n");
    InOrderTraverse(T);
    printf("\n");
    PostOrderTraverse(T);
    printf("\n");
    PostSearch(T,m1,t);
    if(t==1)
        printf("1\n");
    else
        printf("0\n");
    t=0;
    PostSearch(T,m2,t);
    if(t==1)
        printf("1\n");
    else
        printf("0\n");
    InsertBiT(&T,i);
    PreOrderTraverse(T);
    printf("\n");
    InOrderTraverse(T);
    printf("\n");
    PostOrderTraverse(T);
    printf("\n");
    InOrderTraverses(T);
    printf("\n");
    traverse(T);
    Exchange(T);
    PreOrderTraverse(T);
    printf("\n");
    InOrderTraverse(T);
    printf("\n");
    PostOrderTraverse(T);
    printf("\n");
    Exchange(T);
    PreOrderTraverse(T);
    printf("\n");
    InOrderTraverse(T);
    printf("\n");
    PostOrderTraverse(T);
    printf("\n");
    printf("%d\n",Depth(T));
    countieaf(T,k);
    printf("%d\n",k);
    return 0;
}
